#include "node.h"

class Solution {
public:
    //! 1. V1
    // Node* sortInList(Node* head) {
    //     if (head == nullptr || head->next == nullptr) {
    //         return head;
    //     }

    //     //! 将链表节点存储到 vector 中
    //     std::vector<Node*> nodes;
    //     Node* current = head;
    //     while (current != nullptr) {
    //         nodes.push_back(current);
    //         current = current->next;
    //     }

    //     //! 对 vector 进行排序
    //     std::sort(nodes.begin(), nodes.end(), [](const Node* a, const Node* b) {
    //         return a->val < b->val;
    //     });

    //     //! 将排序后的节点重新连接成链表
    //     Node dummy(0);
    //     Node* prev = &dummy;
    //     for (Node* node : nodes) {
    //         prev->next = node;
    //         prev = node;
    //     }
    //     prev->next = nullptr;  // 确保最后一个节点的 next 指针为 nullptr

    //     return dummy.next;
    // }

    //! V2
    Node* sortInList(Node* head) {
        if (head == nullptr || head->next == nullptr) 
            return head;
        std::vector<int> vec;
        Node* ptr = head;
        while (ptr) {
            vec.push_back(ptr->val);
            ptr = ptr->next;
        }
        std::sort(vec.begin(), vec.end());
        ptr = head;
        for (auto it = vec.begin(); it != vec.end(); it++) {
            ptr->val = *it;
            ptr = ptr->next;
        }
        return head;
    }
};